package ArraySecond.SwordOfferItem;

public class NumMatrix_new {
    int[][] sums;

    public NumMatrix_new(int[][] matrix) {
        int m = matrix.length;
        if (m > 0) {
            int n = matrix[0].length;
            sums = new int[m][n + 1];
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    //sum[0][0] sum[1][0] 都是 0,每次都计算某一行的所有的数据之和。
                    sums[i][j + 1] = sums[i][j] + matrix[i][j];
                }
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
            sum += sums[i][col2 + 1] - sums[i][col1];
        }
        return sum;
    }

    public static void main(String[] args) {
        NumMatrix_new numMatrix = new NumMatrix_new(new int[][]{{3, 0, 1, 4, 2}, {5, 6, 3, 2, 1}, {1, 2, 0, 1, 5}, {4, 1, 0, 1, 7}, {1, 0, 3, 0, 5}});
        int i = numMatrix.sumRegion(1, 1, 2, 2);
        System.out.println(i);
    }
}
